package dyyx;

/**
 * 快慢指针 快速定位中间位置 判断链表是否有环
 * 
 * @author dugang
 *
 */
public class FastAndSlowPoint {

	public static void main(String[] args) throws Exception {

		LinkNode node1 = new LinkNode(1);
		LinkNode node2 = new LinkNode(2);
		LinkNode node3 = new LinkNode(3);

		node1.next = node2;
		node2.next = node3;

		System.out.println(middleNode(node1));
		System.out.println(hasCycle(node1));

		node3.next = node1;
		System.out.println(hasCycle(node1));

		LinkNode node4 = new LinkNode(4);
		node3.next = node4;
		System.out.println(middleNode(node1));
		System.out.println(hasCycle(node1));

	}

	public static LinkNode middleNode(LinkNode head) {
		if (head == null) {
			return null;
		}
		LinkNode slow = head;
		LinkNode fast = head;
		while (fast != null) {
			if (fast == null || fast.next == null) {
				break;
			}
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}

	public static boolean hasCycle(LinkNode head) {
		if (head == null || head.next == null) {
			return false;
		}
		LinkNode p = head;
		LinkNode q = head.next;
		while (q != null && q.next != null) {
			if (p == q) {
				return true;
			}
			p = p.next;
			q = q.next.next;
		}
		return false;
	}
}
